/**
 * Dijkstra.java
 *
 * @author Philip Kwok
 */


package SSF.OS.OSPF;


import java.util.*;


// ======================== class SSF.OS.OSPF.Dijkstra ===================== //
/**
 * Dijkstra's shortest path algorithm.  Most of the algorithm is taken from
 * <i>Introduction to Algorithms</i> by Cormen, Leiserson and Rivest.
 */
public class Dijkstra {

  // ......................... constants ........................... //

  // ........................ member data .......................... //

  /** Total number of vertices in the graph. */
  private int num_vertices;

  /** An table of vertices in the graph upon which Dijkstra's algorithm is
   *  being run. */
  private Hashtable vertices;

  /** A vector to be used as a priority queue of vertices by distance. */
  private Vector pq;


  // -------------------------- constructor Dijkstra ----------------------- //
  /**
   * Constructs a new instance of a Dijkstra's algorithm execution given a
   * graph (where vertices are routers and edges are links) and a source
   * vertex.
   */
  public Dijkstra(Hashtable G, String s) {
    vertices = new Hashtable();
    pq = new Vector();

    Vertex dv = null;
    Vector linkinfolist = null;
    String rtrnh = null;
    for (Enumeration enumVar=G.keys(); enumVar.hasMoreElements();) {
      rtrnh = (String)enumVar.nextElement();
      linkinfolist = (Vector)G.get(rtrnh);
      dv = new Vertex(rtrnh,linkinfolist);
      vertices.put(dv.nh,dv);
      pq.addElement(dv);
    }
    // set the predecessor of the source vertex to itself
    Vertex source = (Vertex)vertices.get(s);
    source.pred = source;
    source.dist = 0;
    num_vertices = pq.size();
  }

  // --------------------- Dijkstra.findAllShortestPaths ------------------- //
  /**
   * Returns the true if all the shortest paths can be found. Returns false
   * otherwise.  Refer to RFC2328:16.1.
   */
  public boolean findAllShortestPaths() {

    // - - - - - Stage 1: routers and transit networks - - - - -
    int remaining = num_vertices;
    while (remaining > 0) {
      Vertex u = extractMin();

      for (int i=0; i<u.links.size(); i++) {
        LinkInfo linkinfo = (LinkInfo)u.links.elementAt(i);
        if (linkinfo.TypeOneType == sOSPF.POINT_TO_POINT ||
            linkinfo.TypeOneType == sOSPF.TO_AS_BOUNDARY) {
          // Relax: if the distance from u to its adjacent vertex is less than
          // the distance of the adjacent vertex, set the distance of the
          // adjacent vertex as the distance of u + the distance from u to the
          // adjacent vertex

          // If for any reason a supposed neighboring vertex cannot be found,
          // return false.
          Vertex nbvert = (Vertex)vertices.get(linkinfo.nh);
          if (nbvert == null) {
            // shortest paths not fully computed
            return false;
          }
          Relax(u, nbvert, linkinfo.metric);
        }
      }
      remaining--;
    }


    // - - - - - Stage 2: stub networks - - - - -
    Hashtable newvertices = new Hashtable();
    for (Enumeration enumVar=vertices.elements(); enumVar.hasMoreElements();) {
      Vertex u = (Vertex)enumVar.nextElement();   
      for (int i=0; i<u.links.size(); i++) {
        LinkInfo linkinfo = (LinkInfo)u.links.elementAt(i);
        if (linkinfo.TypeOneType == sOSPF.TO_STUB ||
            linkinfo.TypeOneType == sOSPF.TO_HOST) {
          Vertex stubvertex = new Vertex(linkinfo.nh, null);
          stubvertex.pred = u;
          stubvertex.dist = u.dist + linkinfo.metric;
          // add a leaf to the shortest path tree
          newvertices.put(linkinfo.nh, stubvertex);
        }
      }
    }

    for (Enumeration enumVar=newvertices.keys(); enumVar.hasMoreElements();) {
      String keynh = (String)enumVar.nextElement();
      vertices.put(keynh, newvertices.get(keynh));
    }

    return true;
  }

  // ------------------------- Dijkstra.getDistance ------------------------ //
  /**
   * Returns the distance from the source to the given vertex.
   *
   * @param nhipref  The NHI prefix address of the router (vertex) to find the
   *                 distance to.
  */
  public int getDistance(String nhipref) {
    return ((Vertex)vertices.get(nhipref)).dist;
  }

  // --------------------------- Dijkstra.nextHop -------------------------- //
  /**
   * Returns the NHI prefix of the next hop given a destination NHI prefix.
   *
   * @param src   The NHI prefix address of the router to find the next hop
   *              from.
   * @param dest  The NHI prefix address of the router toward which the next
   *              hop is to be determined.
   */
  public String nextHop(String src, String dest) {
    Vertex v = (Vertex)vertices.get(dest);

    if (v != null && !dest.equals(src)) {
      // trace all the way back to the next hop
      while (v != null && !src.equals(v.pred.nh)) {
        v = v.pred;
      }
    }

    if (v == null) {
      System.err.println("nextHop calculation aborted: " +
                         "table data not yet complete");
      return "-1";
    }

    return v.nh;
  }

  // -------------------------- Dijkstra.extractMin ------------------------ //
  /**
   * Extract the node that has the minimum distance from the root.  If there
   * are ties, take the one with the NHI address which has the smallest
   * lexicographic value.
   */
  private Vertex extractMin() {
    if (pq.size() == 0) {
      return null;
    }
    Vertex minvertex = (Vertex)pq.elementAt(0);
    int minindex = 0;

    for (int i=1; i<pq.size(); i++) {
      Vertex v = (Vertex)pq.elementAt(i);
      if ((v.dist < minvertex.dist) ||
          (v.dist == minvertex.dist && v.nh.compareTo(minvertex.nh) < 0)) {
        minvertex = v;
        minindex = i;
      }
    }
    pq.removeElementAt(minindex);

    return minvertex;
  }

  // ---------------------------- Dijkstra.Relax --------------------------- //
  private void Relax(Vertex src, Vertex dest, int weight) {
    try {
      if ((src.dist != Integer.MAX_VALUE && weight != Integer.MAX_VALUE) &&
          ((dest.dist >  src.dist+weight) || // first sort by cost,
           (dest.dist == src.dist+weight &&  // then lexicographically
            src.nh.compareTo(dest.pred.nh) < 0))) { // by NHI address

        dest.dist = src.dist + weight;
        dest.pred = src;
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  // -------------------------- Dijkstra.computed -------------------------- //
  /**
   * Returns true if all information initiated and shortest paths calculated.
   */
  public boolean computed() {
    // check if all vertices reached
    if (pq.size() != 0) {
      return false;
    }

    // check if all predecessors computed
    for (Enumeration enumVar=vertices.elements(); enumVar.hasMoreElements();) {
      if (((Vertex)enumVar.nextElement()).pred == null) {
        return false;
      }
    }

    return true;
  }



  // ========================== inner class Vertex ========================= //
  /**
   * A node corresponding to a vertex in a graph upon which Dijkstra's
   * algorithm is being run.  It contains information about the vertex which is
   * used by the algorithm but which is not normally kept by the vertex itself.
   */
  class Vertex {

    /** The NHI prefix address of the router or transit network which this
     *  vertex represents. */
    String nh;

    /** The predecessor of this vertex. */
    Vertex pred;

    /** The shortest-path estimate from the root to this vertex. */
    int dist;

    /** The list of link information for the associated router. */
    Vector links;

    Vertex(String rtrnh, Vector l) {
      nh    = rtrnh;
      pred  = null;
      dist  = Integer.MAX_VALUE;
      links = l;
    }

  } // end inner class Vertex


} // end class Dijkstra
